bit tricks

• (a&b)^(a|b) = a^b
• a+b = ((a&b)<<1)+(a^b)
• a^b = a*(1-b)+(1-a)*b (a,b = 0 or 1 일때)
• a^(a+1)^(a+2)^(a+3)=0 이었나?
• i&-i = 최하위비트 끄기
• subset iteration(combination 등) https://fishi.devtail.io/weblog/2015/05/18/common-bitwise-techniques-subset-iterations/
• subset 관련해서 DP하고 있다면 SOSDP도 읽어보자. fast z transform이라고도 하는듯
• 비트연산 뭔가 최대화/최소화 하는건 상위비트부터 처리하는 그리디가 되는경우가 많음. 그리고 이건 트라이와 잘 어울리는 특징.
• AVX2+O3최적화 켜면 빗셋 시간복잡도 /64커팅에서 /256커팅으로 빨라진다는듯. AVX512는 /512일거같은데 지원하는데가 별로 없다는듯?
• mod3 bitset https://codeforces.com/blog/entry/98501?#comment-873190
• subset의 subset iteration? 아무튼 그런 비스무리한 작업은 대충생각하면 O(4^n)같은데 O(3^n)이라고 한다. https://stackoverflow.com/a/68969833 https://www.geeksforgeeks.org/sum-subsets-dynamic-programming/ BOJ23023
• C++20 bit헤더 https://docs.microsoft.com/en-us/cpp/standard-library/bit-functions?view=msvc-170 이제 clz(0)이 UB가 아니라 32와 64로 나온다! 고로 가능하면 bit헤더 함수를 쓰도록 하자